{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Check for Contradictions in Equations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #union-find #graph #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #并查集 #图 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: checkContradictions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #检查方程中的矛盾之处"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个由字符串二维数组&nbsp;<code>equations</code> 和实数数组&nbsp;&nbsp;<code>values</code>&nbsp;，其中 <code>equations[i] = [A<sub>i</sub>, B<sub>i</sub>]</code>，<code>values[i]</code> 表示 <code>A<sub>i</sub> / B<sub>i</sub> = values[i]</code>.。</p>\n",
    "\n",
    "<p>确定方程中是否存在矛盾。<em>如果存在矛盾则返回 <code>true</code>，否则返回 <code>false</code></em>。</p>\n",
    "\n",
    "<p><b>注意</b>:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>当检查两个数字是否相等时，检查它们的&nbsp;<strong>绝对差值&nbsp;</strong>是否小于 <code>10<sup>-5</sup></code>.</li>\n",
    "\t<li>生成的测试用例没有针对精度的用例，即使用 <code>double</code> 就足以解决问题。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> equations = [[\"a\",\"b\"],[\"b\",\"c\"],[\"a\",\"c\"]], values = [3,0.5,1.5]\n",
    "<strong>输出:</strong> false\n",
    "<strong>解释:\n",
    "</strong>给定的方程为: a / b = 3, b / c = 0.5, a / c = 1.5\n",
    "方程中没有矛盾。满足所有方程的一个可能的分配是:\n",
    "a = 3, b = 1 和 c = 2.\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> equations = [[\"le\",\"et\"],[\"le\",\"code\"],[\"code\",\"et\"]], values = [2,5,0.5]\n",
    "<strong>输出:</strong> true\n",
    "<strong>解释:</strong>\n",
    "给定的方程为: le / et = 2, le / code = 5, code / et = 0.5\n",
    "根据前两个方程，我们得到 code / et = 0.4.\n",
    "因为第三个方程是 code / et = 0.5, 所以矛盾。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= equations.length &lt;= 100</code></li>\n",
    "\t<li><code>equations[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= A<sub>i</sub>.length, B<sub>i</sub>.length &lt;= 5</code></li>\n",
    "\t<li><code>A<sub>i</sub></code>, <code>B<sub>i</sub></code> 由小写英文字母组成。</li>\n",
    "\t<li><code>equations.length == values.length</code></li>\n",
    "\t<li><code>0.0 &lt; values[i] &lt;= 10.0</code></li>\n",
    "\t<li><code>values[i]</code> 小数点后最多 2 位。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [check-for-contradictions-in-equations](https://leetcode.cn/problems/check-for-contradictions-in-equations/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [check-for-contradictions-in-equations](https://leetcode.cn/problems/check-for-contradictions-in-equations/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[\"a\",\"b\"],[\"b\",\"c\"],[\"a\",\"c\"]]\\n[3,0.5,1.5]', '[[\"le\",\"et\"],[\"le\",\"code\"],[\"code\",\"et\"]]\\n[2,5,0.5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "      self.fa = {}\n",
    "      self.weight = {}\n",
    "\n",
    "    def find(self, x):\n",
    "      if x != self.fa[x]:\n",
    "        tmp = self.fa[x]\n",
    "        self.fa[x] = self.find(self.fa[x])\n",
    "        self.weight[x] *= self.weight[tmp]\n",
    "      return self.fa[x]\n",
    "\n",
    "    def union(self, x, y, val):\n",
    "      fx, fy = self.find(x), self.find(y)\n",
    "      if fx != fy:\n",
    "        self.fa[fx] = fy\n",
    "        self.weight[fx] = self.weight[y] * val / self.weight[x]\n",
    "\n",
    "    def isconnect(self, x, y):\n",
    "      return x in self.weight and y in self.weight and self.find(x) == self.find(y)\n",
    "\n",
    "    def add(self, x):\n",
    "      if x not in self.fa:\n",
    "        self.fa[x] = x\n",
    "        self.weight[x] = 1.0\n",
    "\n",
    "class Solution:\n",
    "    def checkContradictions(self, equations: List[List[str]], weights: List[float]) -> bool:\n",
    "        DIFF = 0.000001\n",
    "        uf = UnionFind()\n",
    "        for i, (x, y) in enumerate(equations):\n",
    "            uf.add(x)\n",
    "            uf.add(y)\n",
    "            if uf.isconnect(x, y):\n",
    "                if abs(uf.weight[x] / uf.weight[y] - weights[i]) > DIFF:\n",
    "                    return True\n",
    "            uf.union(x, y, weights[i])\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                root = find(p[x])\n",
    "                w[x] *= w[p[x]]\n",
    "                p[x] = root\n",
    "            return p[x]\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        n = 0\n",
    "        for e in equations:\n",
    "            for s in e:\n",
    "                if s not in d:\n",
    "                    d[s] = n\n",
    "                    n += 1\n",
    "        p = list(range(n))\n",
    "        w = [1.0] * n\n",
    "        eps = 1e-5\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            a, b = d[a], d[b]\n",
    "            pa, pb = find(a), find(b)\n",
    "            if pa != pb:\n",
    "                p[pb] = pa\n",
    "                w[pb] = v * w[a] / w[b]\n",
    "            elif abs(v * w[a] - w[b]) >= eps:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:\n",
    "\n",
    "        edges = defaultdict(set)\n",
    "        for j,(x,y) in enumerate(equations):\n",
    "            edges[x].add((y,values[j])) \n",
    "            edges[y].add((x,1/values[j]))  #图中的边一定要成对添加\n",
    "        val = {}\n",
    "        ans = False #初始默认没有矛盾\n",
    "\n",
    "        def dfs(node,v):\n",
    "            nonlocal ans\n",
    "            if ans: #已经有矛盾就不浪费时间了\n",
    "                return\n",
    "            if node in val:\n",
    "                if abs(val[node]-v)>1e-5: #题目明确说不超过1e-5视为相同值\n",
    "                    ans=True\n",
    "                return #搜过的点，不管有没有矛盾，都应直接return，否则程序就会死循环         \n",
    "            val[node]=v\n",
    "            for nei,rat in edges[node]:\n",
    "                dfs(nei,v/rat)\n",
    "        \n",
    "        for x,y in equations:\n",
    "            if x not in val: # 如果x还没有值，y也一定没有，这时说明遇到了一个新的连通分量\n",
    "                dfs(x,1.)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:\n",
    "        def find(x: int) -> int:\n",
    "            if p[x] != x:\n",
    "                root = find(p[x])\n",
    "                w[x] *= w[p[x]]\n",
    "                p[x] = root\n",
    "            return p[x]\n",
    "\n",
    "        d = defaultdict(int)\n",
    "        n = 0\n",
    "        for e in equations:\n",
    "            for s in e:\n",
    "                if s not in d:\n",
    "                    d[s] = n\n",
    "                    n += 1\n",
    "        p = list(range(n))\n",
    "        w = [1.0] * n\n",
    "        eps = 1e-5\n",
    "        for (a, b), v in zip(equations, values):\n",
    "            a, b = d[a], d[b]\n",
    "            pa, pb = find(a), find(b)\n",
    "            if pa != pb:\n",
    "                p[pb] = pa\n",
    "                w[pb] = v * w[a] / w[b]\n",
    "            else:\n",
    "                if abs(v * w[a] - w[b]) >= eps:\n",
    "                    return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def checkContradictions(self, equations: List[List[str]], values: List[float]) -> bool:\n",
    "        # 初始化邻接表\n",
    "        edges = defaultdict(set)\n",
    "        # 填充邻接表\n",
    "        for j, (x, y) in enumerate(equations):\n",
    "            edges[x].add((y, values[j]))\n",
    "            edges[y].add((x, 1 / values[j]))  # 成对添加边\n",
    "            \n",
    "        # 初始化节点值的字典\n",
    "        val = {}\n",
    "        \n",
    "        # 初始化是否有矛盾的标志\n",
    "        ans = False\n",
    "        \n",
    "        # 深度优先搜索函数\n",
    "        def dfs(node, v):\n",
    "            nonlocal ans\n",
    "            if ans:  # 如果已经找到矛盾，直接返回\n",
    "                return\n",
    "            if node in val:\n",
    "                if abs(val[node] - v) > 1e-5:  # 已有值与新值不相等\n",
    "                    ans = True\n",
    "                return\n",
    "            val[node] = v\n",
    "            for nei, rat in edges[node]:\n",
    "                dfs(nei, v / rat)\n",
    "        \n",
    "        # 遍历所有的方程来找出所有连通分量\n",
    "        for x, y in equations:\n",
    "            if x not in val:  # 新的连通分量\n",
    "                dfs(x, 1.)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 测试代码\n",
    "s = Solution()\n",
    "print(s.checkContradictions([[\"a\", \"b\"], [\"b\", \"c\"], [\"c\", \"a\"]], [2.0, 3.0, 6.0]))  # 应输出 True，存在矛盾\n",
    "print(s.checkContradictions([[\"a\", \"b\"], [\"b\", \"c\"], [\"c\", \"a\"]], [2.0, 2.0, 1.0]))  # 应输出 False，不存在矛盾\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
